package com.chj.jz.dp.class02;

public class Code06_MinimumPathSum {
	/**
	 * @param grid:
	 *            a list of lists of integers
	 * @return: An integer, minimizes the sum of all numbers along its path
	 */
	public static int minPathSum(int[][] grid) {
		// write your code here

		int m = grid.length;
		if (m == 0) {
			return 0;
		}

		int n = grid[0].length;
		if (n == 0) {
			return 0;
		}

		int[][] f = new int[2][n];
		int i, j;
		int old = 0, now = 0;
		for (i = 0; i < m; i++) {
			old = now;
			now = 1 - now;
			for (j = 0; j < n; j++) {
				
				if (i == 0 && j == 0) {
					f[now][j] = grid[i][j];
					continue;
				}

				int t = Integer.MAX_VALUE;
				if(i>0) {
					t = Math.min(t, f[old][j]);
				}
				
				if(j > 0) {
					t = Math.min(t, f[now][j - 1]);
				}
				
				f[now][j] = t + grid[i][j];
			}
		}
		
		return f[now][n-1];
	}
	
	public static void main(String[] args) {
		{
			int[][] arr = new int[][] { {1,3,1},{1,5,1},{4,2,1} };
			System.out.println(minPathSum(arr));
		}
		{
			int[][] arr = new int[][] { {1,3,2} };
			System.out.println(minPathSum(arr));
		}
	}
}
